#include<cstdio>
#include<iostream>
using namespace std;
#define LL long long
const int maxn=500005;
const LL INF=0xfffffffff;
long long dp[maxn],s[maxn],a[maxn];
int q[maxn];
bool check1(int j1,int j2,int K)
{
	LL Y1=dp[j1]-s[j1]+j1*a[j1+1];
	LL Y2=dp[j2]-s[j2]+j2*a[j2+1];
	if(Y2-Y1<=K*(a[j2+1]-a[j1+1]))return true;
	return false;
}
bool check2(int j1,int j2,int j3)
{
	LL Y1=dp[j1]-s[j1]+j1*a[j1+1];
	LL Y2=dp[j2]-s[j2]+j2*a[j2+1];
	LL Y3=dp[j3]-s[j3]+j3*a[j3+1];
	if((Y3-Y2)*(a[j2+1]-a[j1+1])<=(Y2-Y1)*(a[j3+1]-a[j2+1]))return true;
	return false;
}
LL min(LL a,LL b)
{
	return a<b?a:b;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int N,K;
		s[0]=0;
		scanf("%d%d",&N,&K);
		for(int i=1;i<=N;i++)
		{
			scanf("%lld",&a[i]);
			s[i]=s[i-1]+a[i];
		}
		//for(int i=1;i<K;i++)dp[i]=INF;
		dp[0]=0;
		int l,r;
		l=0,r=1;q[1]=0;
		for(int i=1;i<=N;i++)
		{
			while(i-q[l+1]>=K&&l<r&&check1(q[l],q[l+1],i))
				l++;
			int j=q[l];
			if(i<K)dp[i]=INF;
			else dp[i]=min(s[i]-a[1]*i,dp[j]+s[i]-s[j]-a[j+1]*(i-j));
			if(i-K+1>0){
			while(l<r&&check2(q[r-1],q[r],i-K+1))r--;
			r++;q[r]=i-K+1;}
		}
		cout<<dp[N]<<endl;
	}
	return 0;
}
